package 栈;

import java.util.Deque;
import java.util.LinkedList;

public class 反转每对括号间的子串 {

    public static String reverseStr(String s){
        //预处理
        int n = s.length();
        int[] pair = new int[n];

        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '('){
                stack.push(i);
            }else if (s.charAt(i) == ')'){
                Integer pop = stack.pop();
                pair[pop] = i;
                pair[i] = pop;
            }
        }
        StringBuffer sb = new StringBuffer();
        int index = 0,step = 1;
        char c;
        while (index < n){
            if ((c = s.charAt(index)) == '(' || c == ')'){
                index = pair[index];
                step = -step;
            }else {
                sb.append(c);
            }
            index += step;
        }

        return sb.toString();
    }


    public static void main(String[] args) {
        System.out.println(reverseStr("a(bc()aaaa()de)f"));
    }
}
